package com.platform.modules.alg.alglib.hdu3486;

public class Hdu3486 {
    public String output = "";

    private final int N = 200010;
    private int a[] = new int[N];
    private int n;
    private int k;
    int F[][] = new int[N][20];
    int lb[] = new int[N];

    void Initlog() {
        lb[0] = -1;
        for (int i = 1; i < N; i++)
            lb[i] = lb[i - 1] + ((i & (i - 1)) > 0 ? 0 : 1);
    }

    void ST(int n) {
        for (int i = 1; i <= n; i++)
            F[i][0] = a[i];
        for (int j = 1; j <= lb[n]; j++)
            for (int i = 1; i <= n - (1 << j) + 1; i++)
                F[i][j] = Math.max(F[i][j - 1], F[i + (1 << (j - 1))][j - 1]);
    }

    int RMQ(int l, int r) {
        int k = lb[r - l + 1];
        return Math.max(F[l][k], F[r - (1 << k) + 1][k]);
    }

    boolean ok(int m) {
        int t = n / m, s = 0;
        for (int i = 0; i < m; i++)
            s += RMQ(t * i + 1, t * i + t);
        return s > k;
    }

    void solve(int n) {
        ST(n);
        int l = 1, r = n, ans = -1;
        while (l <= r) { // 二分找 m
            int m = (l + r) >> 1;
            if (ok(m)) {
                r = m - 1;
                ans = m;
            } else {
                l = m + 1;
            }
        }
        output = ans + "";
    }

    public String cal(String input) {
        Initlog();
        String[] line = input.split("\n");
        String[] words = line[0].split(" ");
        n = Integer.parseInt(words[0]);
        k = Integer.parseInt(words[1]);
        String[] nums = line[1].split(" ");
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(nums[i - 1]);
            sum += a[i];
        }
        if (sum <= k)
            output = "-1";
        else
            solve(n);
        return output;
    }
}
